package cc.wsyw126.java.lintCode;

import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;
/*
 * ��java�е�swap��c�в�һ������Ϊjava�Ĵ��������õ�copy���Ȳ������ñ���Ҳ���Ƕ����൱�ڸ����Ľ�����
 * write by yangDP
 */

public class InvertBT {
    InvertBT left, right;
    public int val;

    public InvertBT(int val) {
        this.val = val;
        this.left = this.right = null;
    }

    public void doInvertBT() {
        Queue<InvertBT> DIQ = new ConcurrentLinkedQueue<InvertBT>();
        DIQ.add(this);
        while (!DIQ.isEmpty()) {
            InvertBT temp = DIQ.remove();
            if (temp.left == null && temp.right != null) {
                temp.left = temp.right;
                temp.right = null;
                DIQ.add(temp.left);
            }
            if (temp.left != null && temp.right == null) {
                temp.right = temp.left;
                temp.left = null;
                DIQ.add(temp.right);
            }
            if (temp.left != null && temp.right != null) {
                InvertBT swap;
                swap = temp.left;
                temp.left = temp.right;
                temp.right = swap;
                DIQ.add(temp.left);
                DIQ.add(temp.right);
                //System.out.print(temp.left.val);
            }
        }
    }


    public void swap(InvertBT x, InvertBT y) {
        InvertBT temp;
        temp = x;
        x = y;
        y = temp;
    }

    public void beforread() {
        if (this != null) {
            System.out.println(this.val);
            if (this.left != null) this.left.beforread();
            if (this.right != null) this.right.beforread();
        }
    }

    public static void main(String[] args) {
        InvertBT bt = new InvertBT(1);
        Queue<InvertBT> q = new ConcurrentLinkedQueue<InvertBT>();
        q.add(bt);
        for (int i = 2; i <= 15; i += 2) {
            InvertBT lf = new InvertBT(i);
            InvertBT rt = new InvertBT(i + 1);
            q.peek().left = lf;
            q.add(lf);
            q.remove().right = rt;
            q.add(rt);
        }
        bt.doInvertBT();
        bt.beforread();
    }

}
